#include <vector>

// 最坏时间复杂度O(N^2)
// 最好时间复杂度O(N^2)
// 空间复杂度为O(1)
// 不稳定的排序 [8,9,8,5,5]

static void selectSort(std::vector<int> &nums)
{
    int n = nums.size();
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        // 在[begin,end]区间内
        // 选出最小的放begin位置
        // 选出最大的放end位置
        int maxi = begin, mini = begin;
        for (int i = begin; i <= end; i++)
        {
            if (nums[i] < nums[mini])
                mini = i;
            if (nums[i] > nums[maxi])
                maxi = i;
        }

        std::swap(nums[begin], nums[mini]);
        // 如果最大值的下标在最左边则需要进行更新
        if (maxi == begin)
        {
            maxi = mini;
        }
        std::swap(nums[maxi], nums[end]);

        ++begin;
        --end;
    }
}
